#include<iostream>
#include<vector>
using namespace std;
/*
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
解题思路：
该题目可以使用回溯算法来实现，首先要构建树形结构，使用index来表示切割回文串的位置,若index=0表示切割的位置是第一个字符的后面切割
首先从根节点开始切割第一个字符，然后从此状态开始向下递归，index变为1，使用回溯和for循环来表示第一次切割的位置为1从而遍历树的每一层
终止条件为切割到最后一个字符的位置也就是index=s.size()时.然后在树层遍历的时候，每次切割就会生成一个子串，
要判断该字串是否满足回文串的条件
*/
vector<vector<string>> result;
vector<string> path;
bool ispartition(string s,int start,int end)
{
    int i=start;
    int j=end;
    while(i<=j)
    {
        if(s[i]!=s[j])
            return false;
        i++;
        j--;
    }
    return true;
}
void backtracking(string s,int index)
{
    //递归终止条件,终止条件为切割到最后一个字符时，该条件是由index=s.size()-1而来，所以终止条件为index>=s.size()
    if(index>=s.size())
    {
        result.push_back(path);
        return;
    }
    //进行树层遍历
    for(int i=index;i<s.size();i++)
    {
        //首先判断分隔出来的子串是否是回文串,子串的范围是index-i
        if(!ispartition(s,index,i))
            continue;
        //若子串是回文串
        path.push_back(s.substr(index,i-index+1));
        //递归遍历剩下的字符串
        backtracking(s,i+1);
        //回溯进行层序遍历
        path.pop_back();
    }
}
vector<vector<string>> partition(string s) {
    backtracking(s,0);
    return result;
}
int main()
{
    cout<<"enter s:"<<endl;
    string s;
    cin>>s;
    result = partition(s);
    for(int i=0;i<result.size();i++)
    {
        for(int j=0;j<result[i].size();j++)
        {
            cout<<result[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}